package 二叉树相关问题.中度题;

import java.util.LinkedList;
import java.util.List;

//非常厉害
public class 好叶子节点的数量 {
    public int countPairs(TreeNode root, int distance) {
        if (root==null)
            return 0;
        List<Integer> lefts = new LinkedList<>();
        List<Integer> rights = new LinkedList<>();
        dfs(root.left,0,lefts);
        dfs(root.right,0,rights);
        int res=0;
        for (Integer left : lefts) {
            for (Integer right : rights) {
                //这里之所以加2，是因为从根节点的左右节点出发求深度
                if (left+right+2<=distance)
                    res++;
            }
        }
        res+=countPairs(root.left,distance);
        res+=countPairs(root.right,distance);
        return res;
    }

    private void dfs(TreeNode node, int depth, List<Integer> list) {
        if (node==null)
            return;
        if (node.left==null && node.right==null)
            list.add(depth);
        dfs(node.left,depth+1,list);
        dfs(node.right,depth+1,list);
    }
}
